/*================================================================
*   Copyright (C) 2024 baichao All rights reserved.
*
*   文件名称：main.c
*   创 建 者：baichao
*   创建日期：2024年01月06日
*   描    述：
*
================================================================*/

/*
 * 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除
 * nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组
 * nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。 请
 * 不要使用除法，且在 O(n) 时间复杂度内完成此题。
 *
 * 示例 1:
 *   输入: nums = [1,2,3,4]
 *   输出: [24,12,8,6]
 *
 * 示例 2:
 *   输入: nums = [-1,1,0,-3,3]
 *   输出: [0,0,9,0,0]
 *
 * 提示：
 *   2 <= nums.length <= 105
 *   -30 <= nums[i] <= 30
 *   保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内
 *
 * 进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（
 * 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）
 */

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

#include <stdio.h>
#include <stdlib.h>

int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
  int* ret = (int*)malloc(numsSize * sizeof(int));
  int* left = (int*)malloc(numsSize * sizeof(int));
  int* right = (int*)malloc(numsSize * sizeof(int));

  if (numsSize == 1) {
    ret[0] = nums[0];
    goto _End;
  }

    left[0] = 1;
  if (numsSize >= 2) {
    left[1] = nums[0];
  }
  // 遍历nums计算出当前位置前缀积和后缀积
  for (int i = 2; i < numsSize; i++) {
    left[i] = left[i - 1] * nums[i - 1];
  }

  right[numsSize - 1] = 1;
  if (numsSize >= 2) {
    right[numsSize - 2] = nums[numsSize - 1];
  }
  for (int i = numsSize - 3; i >= 0; i--) {
    right[i] = nums[i + 1] * right[i + 1];
  }

  // 每个位置的结果就是前缀积*后缀积
  for (int i = 0; i < numsSize; i++) {
    ret[i] = left[i] * right[i];
  }

  *returnSize = numsSize;

_End:
  free(left);
  free(right);
  return ret;
}

int main() {
  int nums[] = {1, 2, 3, 4};
  int returnSize = 0;
  int* ret =
      productExceptSelf(nums, sizeof(nums) / sizeof(nums[0]), &returnSize);
  printf("[");
  for (int i = 0; i < returnSize; i++) {
    printf("%d,", ret[i]);
  }
  printf("]\n");
  return 0;
}